package me.zk.practice1.s;

/**
 * @author zhangkai
 * @date 2023/7/7 16:57
 */
public class LS160 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null || headB==null) return null;
        ListNode l1 = headA,l2 = headB;
        while (l1 != l2){
            l1 = l1 == null?headA:l1.next;
            l2 = l2 == null?headB:l2.next;
        }
        return l1;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA==null || headB==null) return null;
        ListNode l1 = headA,l2 = headB;
        int p1 =0,p2=0;
        while (l1!=null) {
            p1+=1;
            l1=l1.next;
        }
        while (l2!=null) {
            p2+=1;
            l2=l2.next;
        }
        int fast = 0;

        if (p1 > p2) {
            l1 = headA;
            l2 = headB;
            fast = p1-p2;
        } else {
           l1 = headB;
           l2 = headA;
           fast = p2-p1;
        }
        for (int i = 0; i < fast; i++) {
            l1 = l1.next;
        }
        while (l1 != l2) {
            l1 = l1.next;
            l2 = l2.next;
        }
        return l1;
    }
}
